class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        array = []
        stack = []
        for i in range(len(s)):
            if s[i] == '(' or s[i] == ')':
                if stack:
                    if s[i] == ')' and stack[-1][0] == '(':
                        stack.pop()
                    else:
                        stack.append((s[i], i))
                else:
                    stack.append((s[i], i))
            array.append(s[i])
        while stack:
            _, i = stack.pop()
            array[i] = None
        res = ""
        for string in array:
            if string:
                res += string
        return res


if __name__ == '__main__':
    print(Solution().minRemoveToMakeValid("(a(b(c)d)"))
